package BinaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TreeNode {

    private TreeNode left;
    private int val;
    private TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(TreeNode left, int val, TreeNode right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }

    //递归实现前序遍历
    public void prevRecursion(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        prevRecursion(node.left);
        prevRecursion(node.right);
    }


    //递归实现中序遍历
    public void midRecursion(TreeNode node) {
        if (node == null) {
            return;
        }
        midRecursion(node.left);
        System.out.print(node.val + " ");
        midRecursion(node.right);
    }


    //递归实现后序遍历
    public void postRecursion(TreeNode node) {

        if (node == null) {
            return;
        }
        postRecursion(node.left);
        postRecursion(node.right);
        System.out.print(node.val + " ");
    }

    //非递归实现前序遍历
    public List<Integer> prev(TreeNode root) {
        TreeNode node = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                list.add(node.val);
                node = node.left;
            }else {
                TreeNode tp = stack.pop();
                node = tp.right;
            }
        }
        return list;
    }

    //非递归实现中序遍历
    public void mid(TreeNode root) {
        TreeNode node = root;
        LinkedList<TreeNode> stack = new LinkedList<>();

        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);

                node = node.left;
            }else {
                TreeNode tp = stack.pop();
                System.out.print(tp.val + " ");
                node = tp.right;
            }
        }
        System.out.println();

    }

    //非递归实现后序遍历
    public List<Integer> post(TreeNode root) {
        TreeNode node = root;
        TreeNode pop = null;
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        while ( node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            }else {
                TreeNode tp = stack.peek();
                if (tp.right == null || tp.right == pop) {
                    pop = stack.pop();
                    list.add(pop.val);
                }else {
                    node = tp.right;
                }
            }
        }
        return list;
    }

    //判断对称二叉树
    public boolean isSymmetry(TreeNode root) {
        return isSymmetryRecursion(root.left,root.right);
    }

    private boolean isSymmetryRecursion(TreeNode left,TreeNode right) {
        if (left == null && right == null ) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return isSymmetryRecursion(left.left,right.right) && isSymmetryRecursion(left.right,right.left);

    }

    //用递归方式求树的最大深度
    public int maximumDepthRecursion(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = maximumDepth(node.left);
        int r = maximumDepth(node.right);
        return Math.max(l,r) + 1;

    }

    //用非递归方式求树的最大深度
    public int maximumDepth(TreeNode root) {
        TreeNode curr = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int max = 0;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
                if (max < stack.size()) {
                    max = stack.size();
                }
            } else {
                TreeNode peek = stack.peek();
                if ( peek.right == null || peek.right == pop ) {
                    pop = stack.pop();
                }else {
                    curr = peek.right;
                }
            }
        }
        return max;
    }

    //使用层序遍历求树的最大深度
    public int sequenceMaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int depth = 0;
        while ( !queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode tp = queue.poll();
                if (tp.left != null) {
                    queue.offer(tp.left);
                }
                if (tp.right != null) {
                    queue.offer(tp.right);
                }
                //System.out.print(tp.val + " ");
            }
            //System.out.println();
            depth++;
        }
        return depth;
    }

    //使用递归求树的最小深度
    public int minDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = minDepth(node.left);
        int r = minDepth(node.right);
        if (l == 0) {
            return r + 1;
        }
        if (r == 0) {
            return l + 1;
        }

        return Math.min(l,r) + 1;

    }

    //使用层序遍历求得树的最小深度
    public int sequenceMinDepth(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size ; i++) {
                TreeNode poll = queue.poll();
                if (poll.right == null && poll.left == null) {
                    return depth;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return depth;
    }

    //翻转二叉树
    public void rollbackRecursion(TreeNode node) {
        if (node == null) {
            return;
        }
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

        rollbackRecursion(node.left);
        rollbackRecursion(node.right);
    }


}
